Сортирање по разним критеријумима
Као што је речено, за многе типове података (бројеви, ниске, торке) постоји подразумевани поредак, који се користи када при сортирању не прецизирамо критеријум.
У случају да нам подразумевани поредак не одговара или да за податке које сортирамо подразумевани поредак није дефинисан, у библиотечким функцијама сортирања можемо да задамо критеријум сортирања какав год нам одговара.
Често је једина промена која се захтева у односу на подразумевани
поредак то да низ буде сортиран нерастуће уместо неопадајуће. Један
начин да се то постигне је да се изврши обртање низа након сортирања.
Тај додатни посао се може избећи ако се као додатни параметар функцији
сортирања проследи greater<...>.
На пример, вектор бројева a можемо сортирати опадајуће,
позивом sort(begin(a), end(a), greater<int>()).
Разни начини да се библиотечкој функцији сортирања зада специфичан критеријум поређења описани су у задатку Сортирање такмичара.
Када се сортира низ структура или објеката, критеријум је могуће
задати тако што се у самој структури тј. класи дефинише метода која врши
поређење. У језику C++ потребно је дефинисати
оператор <. Та метода треба да врати true
ако и само ако је објекат на ком је позвана строго мањи од објекта који
јој је прослеђен као аргумент (мањи објекти иду испред већих у
сортираном редоследу).
Приликом сортирања било ког типа елемената, функцији за сортирање
могуће је као додатни параметар проследити функцију поређења (било
анонимну, било именовану). Она прима два објекта која треба да упореди и
враћа true ако и само ако јој је први
прослеђен аргумент строго мањи од од другог (мањи објекти иду испред
већих у сортираном редоследу).
Анализа сложености. Библиотечка функција сортирања гарантује да ће број поређења и размена елемената бити \(O(n\log{n})\), где је \(n\) број елемената дела низа који се сортира. Ако је поређење константне сложености, то гарантује да ће сложеност сортирања бити \(O(n\log{n})\). Међутим, ако је функција поређења кориснички дефинисана, она може бити и веће сложености од константне, што значајно може успорити процес сортирања.
Сортирање по разним критеријумима
Као што је речено, за многе типове података (бројеви, ниске, торке) постоји подразумевани поредак, који се користи када при сортирању не прецизирамо критеријум.
У случају да нам подразумевани поредак не одговара или да за податке које сортирамо подразумевани поредак није дефинисан, у библиотечким функцијама сортирања можемо да задамо критеријум сортирања какав год нам одговара.
Често је једина промена која се захтева у односу на подразумевани
поредак то да низ буде сортиран нерастуће уместо неопадајуће. Један
начин да се то постигне је да се изврши обртање низа након сортирања.
Тај додатни посао се може избећи ако се као додатни параметар функцији
сортирања проследи
(x, y) => y.CompareTo(x). На пример, низ бројева
a можемо сортирати опадајуће, позивом
Array.Sort(a, (x, y) => y.CompareTo(x));, а листу
бројева a можемо сортирати опадајуће, позивом
a.Sort((x, y) => y.CompareTo(x));
Разни начини да се библиотечкој функцији сортирања зада специфичан критеријум поређења описани су у задатку Сортирање такмичара.
Када се сортира низ структура или објеката, критеријум је могуће
задати тако што се у самој структури тј. класи дефинише метода која врши
поређење. У језику C# потребно је имплементирати
интерфејс IComparable и дефинисати методу
CompareTo. Функција треба да врати негативан број, нулу или
позитиван број у односу на то да ли је објекат на ком је позвана мањи,
једнак или већи од објекта који јој је прослеђен као аргумент (у
сортираном редоследу мањи објекти иду испред већих).
Приликом сортирања било ког типа елемената, функцији за сортирање могуће је као додатни параметар проследити функцију поређења (било анонимну, било именовану). Она прима два објекта која треба да упореди и враћа негативан број, нулу или позитиван број у односу на то да ли јој је први прослеђени аргумент мањи, једнак или већи од другог прослеђеног аргумента (у сортираном редоследу мањи објекти иду испред већих).
Анализа сложености. Библиотечка функција сортирања гарантује да ће број поређења и размена елемената бити \(O(n\log{n})\), где је \(n\) број елемената дела низа који се сортира. Ако је поређење константне сложености, то гарантује да ће сложеност сортирања бити \(O(n\log{n})\). Међутим, ако је функција поређења кориснички дефинисана, она може бити и веће сложености од константне, што значајно може успорити процес сортирања.